Recently, most application fields such as web click monitoring, sensor data processing, or network traffic analysis need to process a massive unbounded sequence of data elements that are continuously generated. The massive unbounded sequence of data elements that are continuously generated is defined as data stream. In these application fields, a continuous query is used to represent a specific event and monitor whether the corresponding event occurs whenever new data is generated.
Such a continuous query is largely classified into two types as follows in accordance with the intended purpose: the first type is a general purpose query which generates, as a result, a tuple that satisfies the corresponding continuous query and the second type is a detection-only query, which replies only whether newly incoming data (tuple) satisfies the continuous query. In order to process the detection-only query, it is required to know whether the newly incoming tuple satisfies the query, but information on a tuple that satisfies the corresponding query is not required.
A multi-way join query having multiple join predicates is used to combine and monitor the several source data streams and studies about the multi-way join query have conducted. However, most previously known research efforts for continuous query processing use tree-structured execution plans employed in a conventional database management system in order to determine the execution order of binary join operations specified in one continuous query. However, since the selectivity of a join operation under the data stream environment varies depending on the time, the tree-structured execution plans require to be continuously optimized, which causes a serious run-time overhead.
Further, previous researches have mostly focused effort on a general-purpose query, but researches on the detection-only query have been not studied. Therefore, even though the detection-only query is provided, actual join should be performed in order to generate a result of the corresponding query.